package linked_list;

import array_list.MyList;

//双向链表
// 一个正确的 MyLinkedList 应该做到什么
// 1) 得是一个合法的线性表
// 2) 当 head != null 则 last != null
// 反之亦然 当 head == null 则 last == null
// 3) 当 head != null 的时候，则 size > 0
// 同理，当 head == null 的时候，则 size == 0
// 4) size 的值应该 == 通过遍历数出来的结点个数 (从 head 到 last 或者 从 last 到 head）
// 5) 除了 head 和 last 之外，所有的其他结点(node), node.prev != null && node.next != null
// 6) head != null 时，则 head.prev == null，但 head.next 不确定（可以不为 null | size > 1）；也可以为 null | size == 1)
//    last != null 时，则 last.next == null，但 last.prev 不确定（可以不为 null | size > 1）；也可以为 null | size == 1)
// 7) 除了 head 和 last 之外的所有结点(node)，node.prev.next == node && node.next.prev == node
// 8) 当 head.next != null 时，head.next.prev == head
//    当 last.prev != null 时，last.prev.next == last
// 9) 当 size == 1 时，head == last && head != null

public class MyLinkedList implements MyList {
    //维护着三个属性
    //1.链表的头结点
    private MyNode head;
    //2.链表的尾结点
    private MyNode last;
    //3.维护着链表中的元素个数
    private int size;
    //构造方法
    //构造一个空的链表
    public MyLinkedList(){
        this.head = this.last = null;
        this.size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    //尾插，和单链表不同的是：已经记录过尾结点，不用遍历找；因为是双向链表，所以要看prev和next
    //时间复杂度：O(1)
    @Override
    public boolean add(Long e) {
        //先把元素装到结点中
        MyNode node = new MyNode(e);
        //分情况：
        //1.链表中有尾结点
        if(size > 0){
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        }else{
            //2.没有尾结点
            node.prev = null;
            this.head = this.last = node;
        }
        this.size++;
        return true;
    }
    //头插
    //时间复杂度：O(1)
    private boolean addHead(Long e){
        MyNode node = new MyNode(e);
        node.prev = null;
       if(size > 0){
           //链表不为空
           this.head.prev = node;
           node.next = this.head;
           this.head = node;
       }else{
           //链表为空
           node.next = null;
           this.head = this.last = null;
       }
       this.size++;
       return true;
    }

    //根据下标插入
    //1 下标不合法：
    //2 下标合法：
    //  2.1 插入前size == 0 (只有一种情况)
    //  2.2 插入前size == 1
    //      2.2.1 index == 0 头插
    //      2.2.2 index == 1 尾插
    //  2.3 插入前size > 1
    //      2.3.1 index == 0 头插
    //      2.3.2 index == size 尾插
    //      2.3.3 index > 0 && index < size 中间插入
    //时间复杂度O(n)
    @Override
    public void add(int index, Long e) {
        if(index < 0 || index > size){
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }
        if(size == 0){
            add(e);
            return;
        }
        if(size == 1){
            if(index == 0){
                addHead(e);
            }else{
                add(e);
            }
            return;
        }
        if(index == 0){
            addHead(e);
            return;
        }else if(index == size){
            add(e);
            return;
        }
        //size > 1 && 0 < index <size
        //链表插入需要前驱结点
        MyNode prev = this.head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        MyNode cur = prev.next;
        MyNode node = new MyNode(e);
        prev.next = node;
        cur.prev = node;
        node.prev = prev;
        node.next = cur;

        size++;
    }

    //1 下标不合法
    //2 下标合法(不存在size == 0)
    //  2.1 size == 1 头删/尾删
    //  2.2 size > 1
    //      2.2.1 index == 0 头删
    //      2.2.2 index == size - 1 尾删
    //      2.2.3 index > 0 && index < size 中间删除
    //时间复杂度：O(n)
    @Override
    public Long remove(int index) {
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }
        if(size == 1){
            Long e = this.head.val;
            this.head = this.last = null;
            this.size = 0;
            return e;
        }
        //由于size一定是 > 1的，所以，删除头结点之后，一定还有头结点
        //this.head.next != null 等价于 this.size > 1
        if(index == 0){
            Long e = this.head.val;
            this.head = this.head.next;
            //size > 1所以this.head.next一定不是null的
            this.head.prev = null;
            size--;
            return e;
        }
        if(index == size - 1){
            Long e = this.last.val;
            this.last = this.last.prev;
            //由于size一定是 > 1的，所以，删除尾结点之后，一定还有尾结点
            //this.last.prev != null 等价于 this.size > 1
            this.last.next = null;
            size--;
            return e;
        }
        //size > 1 && 0 < index < size - 1
        MyNode cur = this.head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;//一定有cur != null
        }
        Long e = cur.val;
        MyNode prev = cur.prev;
        MyNode next = cur.next;
        //修改引用关系，删除结点cur
        prev.next = next;
        next.prev = prev;
        size--;
        return e;
    }

    //删除从前向后查找过程中第一次遇到的e
    @Override
    public boolean remove(Long e) {
        MyNode cur = this.head;
        for (int i = 0; i < size; i++) {
            //size >= 1
            if(cur.val.equals(e)){
                //是我们要删除的元素
                //index == 0;index == size - 1;剩下的情况
                if(i == 0){
                    this.head = this.head.next;
                    //此时无法判断this.head != null
                    if(this.head != null){
                        this.head.prev = null;
                    }else{
                        this.last = null;
                    }
                    size--;
                    return true;
                }
                if(i == size - 1){
                    this.last = this.last.prev;
                    this.last.next = null;
                    size--;
                    return true;
                }
                //既不是头删也不是尾删
                MyNode prev = cur.prev;
                MyNode next = cur.next;
                prev.next = next;
                next.prev = prev;
                size--;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //时间复杂度:O(n)
    @Override
    public Long get(int index) {
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }
        MyNode cur = this.head;
        for(int i = 0;i < index;i++){
            cur = cur.next;
        }
        return cur.val;
    }

    //时间复杂度：O(n)
    @Override
    public Long set(int index, Long e) {
        if(index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }
        MyNode cur = this.head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        Long oldValue = cur.val;
        cur.val = e;
        return oldValue;
    }

    @Override
    public int indexOf(Long e) {
        int i = 0;
        MyNode cur = this.head;
        while(cur != null){
            if(cur.val.equals(e)){
                return i;
            }
            i++;
            cur = cur.next;
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Long e) {
        int i = size - 1;
        MyNode cur = this.last;
        while(cur != null){
            if(cur.val.equals(e)){
                return i;
            }
            i--;
            cur = cur.prev;
        }
        return -1;
    }

    @Override
    public boolean contains(Long e) {
        return indexOf(e) != -1;
    }

    @Override
    public void clear() {
        this.head = this.last = null;
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private static void assertIsTrue(boolean condition, String message) {
        if (!condition) {
            throw new RuntimeException(message);
        }
    }
    private static void check2(MyLinkedList list) {
        if (list.head == null) {
            assertIsTrue(list.last == null, "head 为 null 时，last 必须是 null");
        } else {
            assertIsTrue(list.last != null, "head 不为 null 时，last 必须不为 null");
        }
    }

    private static void check3(MyLinkedList list) {
        assertIsTrue(list.size >= 0, "size 必须 >= 0");

        if (list.head == null) {
            assertIsTrue(list.size == 0, "head 为 null 时，size 必须是 0");
        } else {
            assertIsTrue(list.size > 0, "head 不为 null 时，size 必须大于 0");
        }
    }

    private static void check4(MyLinkedList list) {
        assertIsTrue(list.size == traverNumberNode(list), "记录的 size 应该和遍历出的 size 相等");
    }

    private static void check5(MyLinkedList list) {
        if (list.size > 1) {
            MyNode cur = list.head.next;
            while (cur != list.last) {
                assertIsTrue(cur.prev != null, "非头尾结点的 prev 不能是 null");
                assertIsTrue(cur.next != null, "非头尾结点的 next 不能是 null");
            }
            cur = cur.next;
        }
    }

    private static void check6(MyLinkedList list) {
        if (list.head != null) {
            assertIsTrue(list.head.prev == null, "头结点的 prev 一定是 null");
            assertIsTrue(list.last.next == null, "尾结点的 next 一定是 null");
            if (list.size == 1) {
                assertIsTrue(list.head.next == null, "size 为 1 时，头节点的 next 一定是 null");
                assertIsTrue(list.last.prev == null, "size 为 1 时，为节点的 prev 一定是 null");
            } else {
                assertIsTrue(list.head.next != null, "size > 1 时，头节点的 next 一定不是 null");
                assertIsTrue(list.last.prev != null, "size > 1 时，尾节点的 prev 一定不是 null");
            }

        }
    }

    private static void check7(MyLinkedList list) {
        if (list.size > 1) {
            MyNode cur = list.head.next;    // 跳过头节点
            while (cur != list.last) {      // 跳过尾结点
                assertIsTrue(cur.prev.next == cur, "非头尾结点的 前驱的 后继是自己");
                assertIsTrue(cur.next.prev == cur, "非头尾结点的 后继的 前驱是自己");
            }
            cur = cur.next;
        }
    }

    private static void check8(MyLinkedList list) {
        if (list.size > 1) {
            assertIsTrue(list.head.next.prev == list.head, "当 head.next != null 时，head.next.prev == head");
            assertIsTrue(list.last.prev.next == list.last, "last.prev != null 时，last.prev.next == last");
        }
    }
    private static void assertPositionMustBe(MyLinkedList list, int index, long e) {
        // 链表中只能遍历去找，要找 index 的结点，意味着 cur 从 head 开始，向后跳  index 步
        MyNode cur = list.head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        // cur 指向 [index] 下标处的结点
        assertIsTrue(cur.val == e, "该位置的值必须是这个值");
    }

    //从前往后遍历确定结点个数
    private static int traverNumberNode(MyLinkedList list) {
        int size = 0;
        for (MyNode cur = list.head; cur != null; cur = cur.next) {
            size++;
        }
        return size;
    }
    private static void assertIsLegal(MyLinkedList list) {
        check2(list);
        check3(list);
        check4(list);
        check5(list);
        check6(list);
        check7(list);
        check8(list);
    }
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        // []
        assertIsLegal(list);

//        list.addHead(100L);
//        // [100]
//        assertIsLegal(list);
//        assertIsTrue(list.size == 1, "size 一定是 1");
//        assertPositionMustBe(list, 0, 100L);

//        list.addHead(200L);
//        // [200, 100]
//        assertIsLegal(list);
//        assertIsTrue(list.size == 2, "size 一定是 2");
//        assertPositionMustBe(list, 0, 200L);
//        assertPositionMustBe(list, 1, 100L);

        assertIsLegal(list);
        list.add(0,100L);
        assertIsLegal(list);
        assertIsTrue(list.size == 1,"size一定是1");
        assertPositionMustBe(list,0,100L);

        //头插200
//        list.add(0,200L);
//        assertIsLegal(list);
//        assertIsTrue(list.size == 2,"size一定是2");
//        assertPositionMustBe(list,0,200L);
        //尾插200
//        list.add(1,200L);
//        assertIsLegal(list);
//        assertIsTrue(list.size == 2,"size一定是2");
//        assertPositionMustBe(list,1,200L);

//        list.add(1,300L);
//        assertIsLegal(list);
//        assertIsTrue(list.size == 3,"size一定是3");
//        assertPositionMustBe(list,0,100L);
//        assertPositionMustBe(list,1,300L);
//        assertPositionMustBe(list,2,200L);

//        list.add(100L);
//        list.add(200L);
//        list.add(300L);
//        list.add(400L);
//        list.add(500L);
//        //[100,200,300,400,500]
//        Long e = list.remove(2);
        //[100,200,400,500]

//        assertIsLegal(list);
//        assertIsTrue(list.size == 4,"size一定是4");
//        assertPositionMustBe(list,0,100L);
//        assertPositionMustBe(list,1,200L);
//        assertPositionMustBe(list,2,400L);
//        assertPositionMustBe(list,3,500L);
//
//        e = list.remove(0);
//        //[200,400,500]
//        assertIsLegal(list);
//        assertIsTrue(list.size == 3,"size一定是3");
//        assertPositionMustBe(list,0,200L);
//        assertPositionMustBe(list,1,400L);
//        assertPositionMustBe(list,2,500L);
//
//        e = list.remove(2);
//        //[200,400]
//        assertIsLegal(list);
//        assertIsTrue(list.size == 2,"size一定是2");
//        assertPositionMustBe(list,0,200L);
//        assertPositionMustBe(list,1,400L);

        System.out.println("测试通过");
    }
}
